技术领域

本发明属于区块链技术领域，特别是涉及一种基于水银承诺面向关键字查询动态索引以及装置。

背景技术

区块链是一个将数据区块以链式数据结构存储与验证的分布式共享账本，具有去中心化、不可篡改、可追溯、公开透明等特点。区块链系统通过点对点网络和共识协议确保网络中诚实的节点具有相同的账本，使用哈希算法、时间戳和Merkle树等技术保护数据的完整性和可溯源性。区块链将前一区块的哈希值存储在后一区块中，若想篡改某个区块中的交易，需要改变该区块以及后续所有区块的值。但由于共识协议的存在，不能掌控51％以上的算力就无法随意篡改交易数据，这保证了区块链的不可篡改性。由于区块链的这些特点，它被广泛应用于多个领域，如物联网、医疗健康、金融系统、信息共享等。

用户可以作为节点加入区块链，保存一个完整的区块链账本。区块链上的数据越来越多，所需要的存储开销越来越大。为了减少节点的存储压力，我们采用链下服务器(SP)与区块链共同存储的混合存储模型，其中SP存储原始数据，区块链存储数据哈希值减少区块链的存储数据。用户需要查询区块链上的数据时，可以向SP发送查询请求。但是SP不被信任，SP可能会恶意地返回不正确不完整地查询结果。所以需要构建一个可验证数据结构(ADS)，由SP和区块链共同维护实现查询结果的可验证。我们之前的工作中针对加密数据的关键字查询设计了KVerkle树，在实际应用中，有些关键字受到很多用户的关注，因此被频繁查询。但现在大多数的可验证查询问题支持对一个或多个区块内的全部数据进行查询，未对查询频繁的关键字的跨区块可验证查询进行研究。对于这些查询频数较高的关键字，SP每收到一次查询请求，都必须遍历本地存储的所有区块，检索匹配查询条件的数据对象。另一方面，交易是源源不断产生的，区块个数在不断增长，检索所有区块会带来较大开销。设计一个针对查询频数较高的关键字的可验证查询结果，可以提高查询效率，减少检索开销。

考虑将区块链系统应用到智慧医疗场景。每个病人的病历会包含多个关键字信息(姓名、就诊医院、诊断、所属地区).例如，医生想查询地区“Hunan”中诊断为“Corona viru”的就诊记录，可输入查询q＝，SP进行关键字检索，如果存在与请求q匹配的数据，则返回这些数据的详细记录。如果不存在，则返回空。

目前在已经有一些针对区块链可验证查询问题的工作。现有方案主要是通过设计一个ADS验证查询结果完整性和正确性的同时减少数据插入开销。C.Zhang等人为每个关键字构建一个索引，因此不需要考虑可搜索的问题。除根节点之外，每个节点均保存一个数据，因此从上至下，逐层添加新的数据。使用变色龙向量承诺实现可验证查找，利用陷门在不改变向量承诺的同时更新向量成员。但是该方法存在以下问题：(1)变色龙向量承诺中没有考虑到隐私的概念，恶意客户端可能会从证明和承诺中了解到有关该向量的额外信息；在我们的问题模型中数据拥有者通过出售数据获利，所以需要保证数据的保密性。当恶意用户通过多次查询获得向量承诺和证明时，可能会从中了解到有关数据的额外信息；(2)没有设置搜索键，因此并没有解决可搜索的动态索引构造问题。

发明内容

为了解决现有方案中的问题，本发明提出了一种基于水银承诺面向关键字查询动态索引以及装置，以实现跨区块直接查询频繁关键字的所有数据对象，并提供验证矢量VO验证查询结果。水银承诺是构建零知识集的，使用软承诺生成承诺时没有绑定任何特定信息，恶意用户也不能获得额外的信息。具体而言，该动态索引树的结构和大小预先确定，利用关键字出现的历史频率估算相关数据对象个数，预留出叶子节点位置。将关键字及其数据对象进行分组合并，同一关键字的分组相邻，确保了节点下关键字集合相似度最大化。使用历史数据初始化树结构，新的数据对象更新原始数据，避免节点的分裂与合并。使用水银向量构建MM Tree，当新数据对象插入时，树中其它节点的向量承诺和成员证明都不需要更新，减少更新开销。

本发明的第一方面，提供一种基于水银承诺面向关键字查询动态索引方法，包括如下步骤：

数据拥有者计算关键字历史查询的次数、当前时间片的频繁关键字集合和包含频繁关键字的历史数据集合；

数据拥有者计算频繁关键字相似度，为每一个所述待分配的历史数据分配一个包含的频繁关键字，所述待分配的历史数据的频繁关键字用于确定所述待分配历史数据能够被快速查询的最佳存储位置；

数据拥有者计算存储组，根据树的度和叶子节点个数确定存储组的个数与容量；

数据拥有者构建优化目标函数与约束条件，所述优化目标函数为：

其中，所述

所述约束条件为：

x

其中，所述x

数据拥有者根据所述优化目标函数和所属条件约束条件，将所述待分配历史数据分配至相应的存储组；

SP通过把水银向量承诺和动态索引树结合起来，构建MM Tree；

数据拥有者计算树中每一个节点存储的素数矩阵、哈希值、软承诺和成员证明；

针对历史数据集合，SP按照Verkle树的构造方法生成MM Tree。令n

{M

其中，所述M

SP插入数据记录，尽管设计了MM Tree的结构，但是新时间片中的数据对象的情况较为复杂，设计基于频数估计和两端聚合的动态数据插入机制。令关键字k

SP生成验证矢量，验证矢量分为验证查询结果正确性和完整性的验证矢量，以及插入一个新数据对象时的插入矢量。MVkle

查询与验证，当SP接收到查询请求q时，如果q中包含频繁关键字，在基于水银向量承诺的动态索引树中检索频繁关键字。从根节点开始，如果当前节点的素数矩阵满足查询条件，则进一步探索其子树。数据需求者收到查询结果R(q)和验证矢量VO

本发明的第二方面，提供了一种基于水银承诺面向关键字查询动态索引装置，包括：

第一计算单元，用于数据拥有者计算关键字历史查询的次数、当前时间片的频繁关键字集合和包含频繁关键字的历史数据集合；

第二计算单元，用于数据拥有者计算频繁关键字相似度，为每一个所述待分配的历史数据分配一个包含的频繁关键字，所述待分配的历史数据的频繁关键字用于确定所述待分配历史数据能够被快速查询的最佳存储位置；

第三计算单元，用于数据拥有者计算存储组，根据树的度和叶子节点个数确定存储组的个数与容量；

第四计算单元，用于数据拥有者构建优化目标函数和约束条件，所述优化目标函数：

其中，所述

所述约束条件为：

其中，所述x

历史数据分配单元，用于数据拥有者根据所述优化目标函数和所述约束条件，将所述待分配历史数据分配至相应的所述存储组；

第五计算单元，用于数据拥有者计算树中每一个节点存储的素数矩阵、哈希值、软承诺和成员证明；

第六计算单元，用于SP按照历史数据集合，按照Verkle树的构造方法生成MMTree；

第七计算单元，用于SP基于频数估计和两端聚合的动态数据插入机制插入数据记录；

第八计算单元，用于SP生成验证矢量，验证矢量分为验证查询结果正确性和完整性的验证矢量，以及插入一个新数据对象时的插入矢量；

第九计算单元，用于SP查询与验证，在基于水银向量承诺的MM Tree中检索频繁关键字，根据查询结果和验证矢量验证结果。

本发明的第三方面，提供了一种电子设备，其特征在于：包括至少一个电子计算机、包括至少一个移动通讯设备和用于与所述电子计算机连接的存储服务器；所述存储服务器存储可被至少一个电子计算机运行的计算机程序，所述程序被所述至少一个电子计算机执行，以使所述至少一个电子计算机能够执行上述的基于水银承诺面向关键字查询动态索引方法。

附图说明

下面结合实施例中的附图更清楚地说明本发明实施例中的技术方案，其中：

图1为系统模型图；

图2为本发明实施例提供的动态索引构建；

图3为本发明实施例提供的基于关键字相似度的对象分配算法示例；

图4为本发明实施例提供的基于增益算法示例；

图5为本发明实施例提供的MM动态索引树节点示例；

图6为本发明实施例提供的MM动态索引树；

图7为本发明实施例提供的MVkle

图8为本发明实施例提供的电子设备的结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

下面从以下四个方面对本发明进行详细说明。1)介绍本发明中的区块链系统模型；2)MM索引的总体架构；3)频繁关键字动态索引的基本结构；4)基于水银向量承诺的动态索引树。

一、区块链系统模型

在介绍本发明的实施例之前，先介绍系统模型图，参考图1，该系统由四个部分组成。数据拥有者为提供数据的用户；数据需求者为发起数据查询的用户；SP为提供查询服务的链下服务器，存储数据加密值；区块链为存储数据哈希值且提供数据验证的分布式账本。参考图1，数据拥有者将加密数据发送给SP构造可验证索引结构，将数据哈希值发送给区块链验证查询结果。数据需求者将查询请求发送给数据拥有者，数据拥有者对其进行编码加密后获得查询矩阵再发送给SP，SP提供查询服务。

将存储在SP的数据抽象为数据对象o＝，其中，id为数据记录唯一标识符id，M为数据记录关键字集合编码加密后的素数矩阵，Ek(data)为数据的加密值，数据拥有者使用数据加密值代替原始数据发送给SP。存储在区块链的数据为o＝，数据拥有者将数据的哈希值hash(data)发送到链上。存储到链上的数据是不可篡改的，所以存储哈希值不仅可以减少链上存储开销，还可以验证数据对象的正确性。数据需求者向数据拥有者发送查询请求q，数据拥有者将编码加密后的素数矩阵M(q)发送给SP进行查询，SP提供查询服务返回满足q的数据记录。查询q为频繁关键字的析取表达式或合取表达式，例如

二、MM索引的总体架构

参照图2，将时间戳按顺序组织成时间片，在t时间片，区块链节点基于t-1时间片中的交易数据T

交易共识阶段：在t-1时间片，区块链节点对交易池中的交易进行打包，生成交易区块，确定频繁关键字以及包含频繁关键字的数据对象。

MM动态索引树构造：在t时间片，根据t-1时间片的交易，构造MM动态索引树结构。区块链节点对索引树结构进行共识，生成索引树区块并且上链。

索引生成阶段：在t+1时间片，区块链节点对到达的数据进行在线的索引构建，插入到上一阶段确定结构的索引树中，生成MM索引树。时间片的结束时间为包含频繁关键字的数据对象的插入总次数达到m。

区块的索引遵循素数编码Verkle树结构，数据存储在Verkle树叶子节点。数据拥有者初始化MM动态索引树，SP在本地按照树节点位置和节点间的父子关系，将收到的树节点构建MM动态索引树结构。根据t时间片确定的频繁关键字集合，遵循数据对象分配算法将数据对象根据频繁关键字存储到叶子节点，从下往上生成素数矩阵和哈希值直到根节点。当新数据到来时，按照数据的动态插入规则将数据对象插入到MM动态索引树的叶子节点。对于无法插入到MM树中的频繁关键字与包含该关键字的数据对象，遵循素数编码Verkle树结构构造小的频繁关键字素数编码Verkle树。

三、频繁关键字动态索引的基本结构

1)动态索引的数据对象分配问题

本发明的一个实施例，提供了一种动态索引的数据对象分配方法，本发明的方法实施例用于上述的系统模型，本方法包括如下步骤：

步骤S100、数据拥有者计算关键字历史查询的次数、当前时间片的频繁关键字集合和包含频繁关键字的历史数据集合；

步骤S200、数据拥有者计算频繁关键字相似度，为每一个所述待分配的历史数据分配一个包含的频繁关键字，所述待分配的历史数据的频繁关键字用于确定所述待分配历史数据能够被快速查询的最佳存储位置；

步骤S300、数据拥有者计算存储组，根据树的度和叶子节点个数确定存储组的个数与容量；

步骤S400、数据拥有者构建优化目标函数和约束条件，所述优化目标函数：

其中，所述

所述约束条件为：

表示每个组g

表示同一个数据对象在所有组中的分配次数等于其关联的频繁关键字个数|K(o

x

表示当数据对象o

步骤S500、数据拥有者根据优化目标函数和约束条件，将待分配历史数据分配至相应的存储组。

在上述步骤S100至步骤S500，数据拥有者首先为存储组设置一个存储容量，系统中所有数据记录分配到该存储组的个数总和要达到该容量，可以避免因为存储空间的浪费。然后定义了在每个组都满足存储容量S的条件下最大化组内与相邻组间的频繁关键字平均相似度的优化目标函数，进而实现数据记录的分配，在满足存储容量的条件下，最大化关键字相似度。

以下充分说明上述步骤S100至步骤S500：

定义索引树中共有l个叶子节点，存在树的度fanout为S，所有非叶子节点都包含S个子节点。为了便于分配，将叶子节点进行分组。将叶子节点与其所有兄弟节点分成一个组往上构建父节点，所有的叶子节点可划分为Z＝l/S个分组。当某个关键字k

定义1：通过历史查询计算出关键字k

定义2：用O＝{o

定义3：本发明的相似度计量方法与汉明距离类似，汉明距离为两个等长字符串对应位置的不同元素的个数。频繁关键字k

在度为S的动态索引树中，我们将具有同样父节点的所有叶子节点作为一个组，用来存储数据对象。下面给出组的具体定义。

定义4：用G＝{g

相邻存储组之间的频繁关键字平均相似度越大，则查询效率越高。设k

具体的，基于上述四个定义，本方法实施例步骤如下：

构建优化目标函数为：

对于公式(3)，给定频繁关键字集合K＝{k

约束条件为：

x

其中，对于公式(4)：每个组g

在步骤S500构建优化目标函数和约束条件之后，需要证明本方法实施提出的基于最大相似度的数据对象分配问题是NP难问题，才能实现求解。

证明过程：广义多分配问题(GMAP)[3]是已知的NP难问题，我们将广义多分配问题(GMAP)规约到基于最大相似度的数据对象分配问题中的一种特殊情况，证明我们的问题是NP难问题。一个固定大小的广义多分配问题可以描述为：给定一个具有n项集合IT＝{it

x

对于给定的GMAP实例，我们可以将其在多项式时间内转换为基于最大相似度的数据对象分配问题的一个实例：GMAP实例中的物品it

由于我们的目标是求组内平均相似度Sim(g

通过以上映射，GMAP实例优化目标与我们问题的特殊情况一致，因此最大相似度的数据对象分配问题是NP难问题。

2)数据对象分配方法

具体的，本发明实施例提供了以下两种方法来进行分配计算：

第一种方法，基于关键字相似度的对象分配算法求解：

基于最大相似度的数据对象分配问题是NP难问题，所以只能为数据对象的分配找一个近似解。优化目标是最大化组内和相邻组间频繁关键字平均相似度，一个最直接的想法是优先选择包含同一个关键字的数据对象，将其分配到同一个存储组中。如果该关键字的数据对象全部分配完或者该存储组容量达到阈值，则选择包含最大相似度关键字的数据对象继续分配。

如算法1所示，首先将K中的关键字按照其关联的数据对象的数目进行排序(第1行)。如果K不为空，依次对G＝{g

时间复杂度分析：第1行对所有关键字进行排序的时间开销为O(mlogm)。第9行的开销为O(m

为了便于理解，给出一个具体实例。参照图3，存储组个数为3，存储组的最大容量为3。g

第二种方法，基于增益的对象分配算法求解：

优化目标是最大化组内和相邻组间频繁关键字平均相似度，但又要满足每个存储组最大容量的要求。基于关键字相似度的算法在选择数据对象时，仅仅考虑了与当前选择的频繁关键字之间的相似度，没有考虑整个存储组中关键字的总相似度。所以我们提出基于增益的算法。假设选择存储组g

在数据对象基础存储单位相同的情况下，优先选择Δsim大的数据对象有利于在保证存储容量阈值的限制下最大化总相似度。

定理2：第s步将数据对象o

综上所述，对于第s步将数据对象o

根据定理2，如果在s步选择数据对象-关键字对，那么在s+1步也会选择包含该关键字的数据对象；因此关键字是连续分配的。所以我们提出基于增益的贪心算法，每次选择Δsim最大的关键字k，然后将其包含的数据对象O(k)进行连续分配。算法2描述了基于增益的数据对象分配算法；算法步骤和算法1类似，如果K不为空，依次对G＝{g

时间复杂度分析：第9行需要选择总增益最大的关键字，因此时间开销为O(m

为了便于理解，这里给出一个具体实例。参照图4，使用图3中一样的数据。首先选择存储组g

四、基于水银向量承诺的动态索引树

将水银向量承诺和动态索引树结合，提出基于水银向量承诺的动态索引树。数据拥有者使用水银向量承诺中的软承诺为每个节点生成一个软承诺对，该软承诺对不绑定任何特定信息。当向量中第j个元素更新，向量的软承诺对不会改变，只生成一个新的成员证明τ

基于水银向量承诺的动态索引树是一个q元树，所有数据存储在叶子节点中。叶子节点包含数据对象素数矩阵、素数矩阵哈希值、数据加密值和成员证明。参考图5，索引树中位于pos处的非叶子节点结构由5个部分组成：{M

可以注意到，每个节点的软承诺对是由节点位置pos预先确定的。在新数据对象插入阶段，软承诺对保持不变，但可以为新数据对象生成成员证明。为了防止不可信的第三方返回错误的查询结果，数据需求者可以使用软承诺对和成员证明验证查询结果的正确性。

参考图6，图6(b)中为基于水银向量承诺的索引树。当数据对象插入到节点n

1)动态场景下数据对象的插入

动态场景下数据对象的插入，尽管设计了动态索引树的结构，但是新时间片中的数据对象的情况较为复杂，典型的特殊情况如下：

①给定频繁关键字，包含该频繁关键字的数据对象的个数可能比预期的要多，这样多余的对象没有合适的存储位置；

②给定频繁关键字，包含该频繁关键字的数据对象的个数可能比预期的要少，这样就会造成原有存储位置被浪费的现象；

④出现了新的频繁关键字，显然这些新的频繁关键字在原索引结构中并没有分配位置。

为此，设计基于频数估计和两端聚合的动态数据插入机制。令关键字k

对于新的频繁关键字k

基于上述规则，S(k

为了便于理解，这里给出一个具体实例。参考图7，素数集合P＝{2,3,5,7,11,13,17,19,23}，编码素数矩阵的元素个数为6。在动态索引树中频繁关键字k

2)动态索引树初始化与数据插入

数据拥有者首先生成一对公钥pk和私钥sk对以及PRF密钥sk

当数据拥有者将动态索引树中所有的非叶子节点初始化发送给SP后，SP在本地构建出一棵MVkle

当新数据到来时，SP按照插入规则将新到来的数据对象插入到MVkle

MVkle

为了便于理解，这里提供一个具体实例。参考图7，当数据对象o

智能合约接收到UpdVO后，先验证新数据M(k

3)验证矢量的生成

MVkle

为了便于理解，这里提供一个具体实例。数据需求者发送的查询请求子句为q＝grand，编码为M(q)＝[17 7 11 5 13 0]

4)查询和验证

当SP接收到查询请求q时，如果q中包含频繁关键字，在基于水银向量承诺的动态索引树中检索频繁关键字。从根节点开始，如果当前节点的素数矩阵满足查询条件，则进一步探索其子树。此外，将相应的向量承诺对(C

数据需求者收到查询结果R(q)和验证矢量VO

为了便于理解，这里提供一个具体实例。轻节点收到查询结果为R(q)的验证矢量VO

以下提供实验结果：

实验平台(环境)：实验的硬件环境是AMD Ryzen 7 5800H with Radeon Graphics3.20GHz，RAM为16.0GB的PC机，操作系统为Windows10。使用Java语言进行编写，为所有的数据构建一个区块。

实验数据：为了简化实验过程，区块打包的数据可以使用代码进行随机生成，测试使用的关键字数据集为谷歌的10000个最常用英语单词。

对比算法：实验比较Merkle哈希树、KVerkle树和动态MM树。针对每个索引，对比索引树构建算法、查询算法、结果验证算法以及数据插入算法。

性能指标：使用存储开销、时间开销作为评价指标。其中存储开销包括构建索引树时所占用的内存和验证矢量的大小。时间开销包括：构建索引树的时间开销、查询区块中数据的时间开销、验证查询结果的时间开销、插入新数据的时间开销。对于每个实验，我们随机生成20个实验结果并报告平均结果。

参数：测试数据数量和树的扇出对性能指标的影响。交易数量的取值为[64,128,…,8192,16383]，默认值设为1024。ADS的扇出取值为[2,4,8,…,1024],Merkle哈希树的扇出确定为4。为了公平对比，我们将其它ADS的扇出默认值设置为4。

参照图8，本发明还提供一种电子设备，包括：电子计算机、移动通讯设备、存储服务器及存储在存储服务器上并可在电子计算机上运行的计算机程序，电子计算机运行计算机程序可实现上述的基于水银承诺面向关键字查询动态索引且存储在存储服务器中。上述移动通讯设备可通过网络通信向电子计算机发送计算机可执行查询指令，电子计算机在存储服务器上执行查询操作。